Improvements in the processing speeds of CPUs (Central Processing Units) have been accompanied by increasing complexity in CPU configurations. For example, CPUs comprise computation units, instruction units, cache memory, cache controller units, and various registers. With advances in integration technology in recent years, there have been trends toward incorporation of CPUs on a single chip, and there have been demands for simplified circuit configurations and faster operation for each unit in a CPU.
In such a computation unit, there exist adders/subtractors, logical computation (operation) circuits, shift circuits, and similar. Of these, the logic operation circuits handle logic operations to compute logical AND and logical OR results, performing logic operations on a pair of input operands. For example, a logic operation circuit 200 is configured as shown in FIG. 15. As in FIG. 15, one of the input operands is the a-bus, and the other is the b-bus. In this explanation it is assumed that each operand has 8 bits. That is, the a-bus and b-bus for the operands consist of data bits a0 to a7 and a parity bit ap, and data bits b0 to b7 and a parity bit bp.
The first input port 100 receives data a0 to a7 of an operand, and the first parity port 102 receives the parity bit ap. The second input port 104 receives the data b0 to b7 of an operand, and the second parity port 106 receives the parity bit bp. The instruction port 108 receives logic operation instructions from an instruction unit (not shown). To facilitate the explanation, in logic operations, instructions in cases in which the instruction independently inverts both the operands are taken to be the eight instructions shown in FIG. 16.
This logic operation circuit 200 has an AND circuit 130, a OR circuit 132, and a selector 140. The pair of operands a-bus and b-bus are input, via the EOR circuits 112 to 118, to both the AND circuit 130 and the OR circuit 132.
On the other hand, logic operation instructions at the instruction port 108 are decoded by a decoder 110 and input to the selector 140 and to the EOR circuits 112 to 118. The selector 140 outputs as data the operation result of either the AND circuit 130 or the OR circuit 132, according to the instruction. The EOR circuits 112 to 118 invert the input data and output the results to the AND circuit 130 and OR circuit 132, according to the instruction.
When instructions for logical AND and logical OR operations which invert the input data are processed, in order to minimize the delay time, a parity prediction circuit 134 is provided for each instruction.
Here, parity prediction in basic logic operations is explained. In logical AND/OR operations, as shown in FIG. 15, the parity bit ap is treated as the number of bit “1” on the a-bus, and the parity bit bp is treated as the number of bit “1” on the b-bus. The parity prediction performs a prediction by taking into how increase or decrease the total bit number of “1” on the bus.
FIG. 17 explains the truth table for an AND operation for one bit and conditions of parity inversion. In FIG. 17, the four patterns for input of “0” and “1” as the two inputs ‘a’ and ‘b’, the result ‘x’ of an AND operation on the two inputs ‘a’ and ‘b’, a parity change signal PCand, and comments on changes in the number of “1” in the two inputs and the operation results are shown. PCand in FIG. 17 is the condition for change in parity due to a one-bit AND operation; the total number of “1” bits in the input data ‘a’ and ‘b’ and the total number of “1” bits in the AND operation result ‘x’ are compared, and as indicated in the Comment column, if the number of bit “1” in the two inputs is different from the number of bit “1” in the operation result ‘x’, the result is “1”, and if the same, the result is “0”.
More specifically, in FIG. 17, if a=0 and b=0 then the AND operation result is x=0, and there is no change between the number of “1” bits and the operation result, so that PCand=0; if a=0 and b=1, the AND operation result is x=0, but there is a change from the total number of “1” bits, which is 1, to the operation result x=0, so that PCand=1.
The total number of “1” bits on the a-bus and b-bus can be determined by taking the EOR of the a-bus parity bit ap and the b-bus parity bit bp. An EOR result of “0” indicates that the sum is an even number, and an EOR result of “1” indicates that the sum is an odd number. From FIG. 17, it is seen that PCand=a|b (the OR of a and b).
FIG. 18 explains the truth table for an OR operation for one bit and conditions of parity inversion. In FIG. 18, similarly to FIG. 17, the four patterns for input of “0” and “1” as the two inputs ‘a’ and ‘b’, the result ‘x’ of an OR operation on the two inputs ‘a’ and ‘b’, a parity change signal PCor, and comments on changes in the number of “1” in the two inputs and the operation results are shown. PCor in FIG. 18 is the condition for change in parity due to a one-bit OR operation; the total number of “1” bits in the input data ‘a’ and ‘b’ and the total number of “1” bits in the OR operation result ‘x’ are compared, and as indicated in the Comment column, if the number of “1” bits in the two inputs is different from the number of “1” bits in the operation result ‘x’, the result is “1”, and if the same, the result is “0”.
More specifically, in FIG. 18, if a=0 and b=0 then the OR operation result is x=0, and there is no change between the number of “1” bits and the operation result, so that PCor=0; if a=1 and b=1, the OR operation result is x=1, but there is a change from the total number of “1” bits from “2” to the operation result x=1, so that PCor=1. From FIG. 18, it is seen that PCor=a&b (the AND of a and b).
The total number of “1” bits in these two inputs can be determined from the EOR (exclusive OR) of the parity bits ap and bp. An EOR result for ap and bp of “0” indicates that the sum is an even number, and an EOR result for ap and bp of “1” indicates that the sum is an odd number.
For example, when the bus width is 8 bits, and a parity bit is added in byte (8-bit) units, the AND operation parity prediction bit rpand is as indicated by equation (1) below. Here, ap, bp, and rp (the predicted parity bit) are odd parity.
                    [                  Equation          ⁢                                          ⁢          1                ]                                                                                                                rp                                                                                          ⁢                  and                                            =                                                (                                                            pc                                              and                        ⁢                                                                                                  ⁢                        7                                                              ⊕                    …                    ⊕                                          pc                                              and                        ⁢                                                                                                  ⁢                        0                                                                              )                                ⊕                                                      (                                          ap                      ⊕                      bp                                        )                                    _                                                                                                        =                                                (                                                            a                      7                                        ❘                                          b                      7                                                        )                                ⊕                …                ⊕                                  (                                                            a                      0                                        ❘                                          b                      0                                                        )                                ⊕                                                      (                                          ap                      ⊕                      bp                                        )                                    _                                                                                                        =                                                pchg                  and                                ⊕                                                      (                                          ap                      ⊕                      bp                                        )                                    _                                                                                        (        1        )            
From equation (1), the inversion condition signal pchgand is as given by equation (2) below.
[Equation 2]pchgand=(a7|b7)⊕ . . . ⊕(a0|b0)  (2)
Similarly, the OR operation predicted parity bit rpor is as given by equation (3) below. Here, ap, bp, and rp (the predicted parity bit) are odd parity.
                    [                  Equation          ⁢                                          ⁢          3                ]                                                                                                                rp                or                            =                                                (                                                            pc                                              or                        ⁢                                                                                                  ⁢                        7                                                              ⊕                    …                    ⊕                                          pc                                              or                        ⁢                                                                                                  ⁢                        0                                                                              )                                ⊕                                                      (                                          ap                      ⊕                      bp                                        )                                    _                                                                                                        =                                                (                                                                                    a                        7                                            &                                        ⁢                                                                                  ⁢                                          b                      7                                                        )                                ⊕                …                ⊕                                  (                                                                                    a                        0                                            &                                        ⁢                                                                                  ⁢                                          b                      0                                                        )                                ⊕                                                      (                                          ap                      ⊕                      bp                                        )                                    _                                                                                                        =                                                pchg                  or                                ⊕                                                      (                                          ap                      ⊕                      bp                                        )                                    _                                                                                        (        3        )            
From equation (3), the inversion condition signal pchgor is as given by equation (4) below.
[Equation 4]pchgor=(a7&b7)⊕ . . . ⊕(a0&b0)   (4)
Then, the following obtains.
In the case of andn/orn to invert the b-bus data for the sub signal, the predicted parity bits rpandn and rporn are as indicated by equation (5) below.
                    [                  Equation          ⁢                                          ⁢          5                ]                                                                                                                rp                andn                            ⁢                                                          =                                                          ⁢                                                                    (                                                                  a                        7                                            ⁢                                                                                          ❘                                                                                          ⁢                                                                        b                          7                                                _                                                              )                                    ⊕                  …                  ⊕                                      (                                                                  a                        0                                            ⁢                                                                                          ❘                                                                                          ⁢                                                                        b                          0                                                _                                                              )                                    ⊕                  ap                  ⊕                  bp                                _                                                                                                                          rp                  orn                                =                                                                  ⁢                                                                            (                                                                                                    a                            7                                                    &                                                ⁢                                                                                                  ⁢                                                                              b                            7                                                    _                                                                    )                                        ⊕                    …                    ⊕                                          (                                                                                                    a                            0                                                    &                                                ⁢                                                                                                  ⁢                                                                              b                            0                                                    _                                                                    )                                        ⊕                    ap                    ⊕                    bp                                    _                                            ⁢                                                                                                      (        5        )            
As described above, in a parity prediction circuit, the prediction logic of generation of inversion condition signals differs for each instruction. However, having parity prediction logic for eight instructions in FIG. 16 greatly increases the circuit scale. For this reason, in the following the de Morgan theorem of equation (6) below is applied to reduce the circuit scale.
                    [                  Equation          ⁢                                          ⁢          6                ]                                                                                                                a                _                            &                        ⁢            b                    =                                    a              ❘                              b                _                                      _                          ⁢                                  ⁢                                            a              _                        ❘            b                    =                                                    a                &                            ⁢                              b                _                                      _                          ⁢                                  ⁢                                                            a                _                            &                        ⁢                          b              _                                =                                    a              ❘              b                        _                          ⁢                                  ⁢                                            a              _                        ❘                          b              _                                =                                                    a                &                            ⁢              b                        _                                              (        6        )            
That is, using the relation in equation (6), a circuit is shared for AND instructions for andn1 and orn, for orn1 and andn, for andn2 and or, and for orn2 and in FIG. 16, so that the circuit scale is reduced. FIG. 19 shows an example of the configuration of a first prior art parity prediction circuit 134 to which this relation is applied.
The parity prediction circuit 134 of FIG. 19 has a first OR prediction logic circuit 200, which generates an OR logic inversion condition signal pchgor from inputs ‘a’ and ‘b’; a first AND prediction logic circuit 202, which generates an AND logic inversion condition signal pchgand from inputs ‘a’ and ‘b’; a second OR prediction logic circuit 204, which generates an OR logic inversion condition signal pchgorn from input ‘a’ and the inverse of ‘b’ resulting when the inverter 210 inverts input ‘b’; a second AND prediction logic circuit 206, which generates an AND logic inversion condition signal pchgandn from input ‘a’ and the inverse of ‘b’ resulting when the inverter 212 inverts input ‘b’; and a selector 208, which selects an output of these circuits 200 to 206 using the decoding signal of the above-described decoder 110.
In order to obtain the total number of bit “1” in the above-described a-bus and b-bus data, the parity prediction circuit 134 has an inverted EOR circuit 220 which performs an EOR logic operation on the parity bit ap of the a-bus and the parity bit bp of the b-bus and inverts the result, an EOR circuit 224 which performs an EOR logic operation on the output of the EOR circuit 220 and the inverted parity signal (when a parity is added to data with odd number of bits, this signal is set to “1” on certain instructions), and an EOR circuit 226 which performs an EOR logic operation on the output of the selector 208 (inversion condition signal) and the output of the EOR circuit 224.
That is, the first OR prediction logic circuit 200 computes pchgor of equation (4), the second OR prediction logic circuit 204 computes pchgorn similarly to equation (4), the first AND prediction logic circuit 202 computes pchgand of equation (2), and the second AND prediction logic circuit 206 computes pchgandn similarly to equation (2).
Hence one of rpand, rpor, rporn, rpandn of equation (1), equation (3) and equation (5) is output from EOR circuit 226 as the parity prediction signal rp, according to the logic operation instruction of FIG. 16 (see for example Japanese Patent Laid-open No. S58-029054, FIG. 2).
On the other hand, in a second parity prediction circuit 134 of the prior art shown in FIG. 20, a first OR prediction logic circuit 200 which generates OR logic inversion condition signals from two inputs, a first AND prediction logic circuit 202 which generates AND logic inversion condition signals from two inputs, and a selector 208 are provided, and moreover EOR circuits 214, 216 are provided before the parity prediction circuits, as logic for data inversion. Otherwise the configuration is the same as in FIG. 19. By this means, the number of prediction logic circuits can be halved.
In the first technology of the prior art shown in FIG. 19, four prediction logic circuits are required. As explained above, in order to perform the calculations of equation (2) and equation (4), these circuits require, for example, 15 logic operation elements even for 8-bit data. If the number of data bits is for example 64 bits, then a configuration eight times greater is required, so that the scale of the circuit configuration becomes enormous.
On the other hand, in the second technology of the prior art shown in FIG. 20, because there are two prediction logic circuits, the circuit configuration is small compared with the first technology of the prior art, but the inversion of input data is placed before the parity prediction circuits, and so to this extent the delay is increased. In particular, when the data bit length is long, there is the problem that the delay of signals (in FIG. 20, inv a and inv b) to control inversion of data from the decoder 110 which decodes instructions in FIG. 16 becomes extremely long.
Hence an object of this invention is to provide a logic operation parity prediction circuit and logic operation circuit to rapidly perform parity prediction, while reducing the circuit scale.
A further object of the invention is to provide a logic operation parity prediction circuit and logic operation circuit to reduce the circuit scale of the hardware of logic operation circuits having parity prediction functions.
Still a further object of the invention is to provide a logic operation parity prediction circuit and logic operation circuit to realize faster operation of logic operation circuits having parity prediction functions.